package com.desin.modle.datastruct.algo.gaoji.tuopusorting;

import java.util.LinkedList;

public class Solution {
    private int v;//顶点个数

    private LinkedList<Integer> adj[];//领接表

    public Solution(int v){
        this.v = v;
        for(int i=0;i<v;i++){
            adj[i] = new LinkedList<Integer>();
        }
    }

    //s->t
    public void put(int s,int t){
        adj[s].add(t);
    }

    public void kahn(){
        //初始统计各个顶点的入度，初始都为0
        int[] ingree = new int[v];

        for(int i=0;i<v;i++){
            for(int j=0;j<adj[i].size();j++){
                Integer integer = adj[i].get(j);
                ingree[integer]++;
            }
        }

        LinkedList<Integer> resultList = new LinkedList<Integer>();

        for(int i=0;i<v;i++){
            if(ingree[i]==0){
                resultList.add(i);
            }
        }

        while (!resultList.isEmpty()){
            Integer remove = resultList.remove();
            System.out.print("-->" + remove);

            for(int i=0;i<adj[remove].size();i++){
                Integer integer = adj[remove].get(i);
                ingree[integer]--;

                if(ingree[integer]==0){
                    resultList.add(integer);
                }
            }
        }

        System.out.println();
        boolean cycleFlag = false;

        for(int i=0;i<v;i++){
            if(ingree[i]!=0){
                cycleFlag=true;
                break;
            }
        }

        if(cycleFlag){
            System.out.println("有环");
        }else{
            System.out.println("无环");
        }
    }

    public void topoSortByDfs(){
        //记录某个顶点的入度顶点
        LinkedList<Integer> reverseAdj[] = new LinkedList[v];

        //初始化逆邻接表
        for(int i=0;i<v;i++){
            reverseAdj[i] = new LinkedList<>();
        }

        //构建逆领接表
        for(int i=0;i<v;i++){
            for(int j=0;j<adj[i].size();j++){
                Integer integer = adj[i].get(j);
                reverseAdj[integer].add(i);
            }
        }

        //记录是否被访问过
        boolean visited[] = new boolean[v];

        for(int i=0;i<v;i++){
            if(visited[i]==false){
                visited[i] = true;
                dfs(i,reverseAdj,visited);
            }
        }
    }

    private void dfs(int i, LinkedList<Integer>[] reverseAdj, boolean[] visited) {
        for(int j=0;j<reverseAdj[i].size();j++){
            Integer cur = reverseAdj[i].get(j);//遍历入度顶点
            if(visited[cur]==true){
                continue;
            }
            visited[cur] = true;
            dfs(cur,reverseAdj,visited);
        }
        System.out.print("-->"+ i);
    }
}
